1. Field of the Invention
The present disclosure relates generally to link state protocols, and more particularly to systems and methods for preventing router adjacencies from failing due to bad link state advertisement requests.
2. Description of Related Art
In a packet network, “nodes” or “routers” share network topology and reachability information that allows each node or router to forward packets toward their respective destination networks. For networks defined using the Internet Protocol, each node is provisioned with a network address that identifies the particular network the system is on, and with a system or host address that uniquely identifies the node. These addresses are advertised among neighboring nodes to allow each router to build a “tree” with itself as the root node and next-hop paths from itself to every address on the network.
Routers use IP addresses to forward routed traffic on a packet network according to a routing protocol. Some common routing protocols in use today include Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), and Border Gateway Protocol (BGP). OSPF is further described in Internet Engineering Task Force (IETF) Request for Comments (RFC) 2328, “OSPF Version 2,” by J. Moy, April 1998, and IETF RFC 2740, “OSPF for IPv6,” R. Coltun, December 1999, both of which are incorporated herein by reference. IS-IS is further described in the International Organization for Standardization (ISO) document ISO 8473, “Intermediate System to Intermediate System Routing Information Exchange Protocol for Providing the Connectionless-mode Network Service,” ISO/IEC10589:2002, 2nd Ed., which is incorporated herein by reference. BGP is further described in IETF RFC 4271, “A Border Gateway Protocol 4 (BGP-4),” by Y. Rekhter et al., January 2006, and is incorporated herein by reference.
OSPF and IS-IS are examples of link-state protocols. A “link” can be considered to be an interface or port on a router (although some such protocols can be used to distribute other information). The state of that link contains a description of the interface and what routers/networks are reachable through that link. In OSPF, a link-state database contains the IP address of the interface/device, the subnet mask (which indicates what portion of an IP address is the network address) and other information describing the network, a list of routers connected to that network, a cost of sending packets across that interface, etc.
OSPF routers use link-state advertisements (LSAs) to share information from their link-state databases with neighboring routers in the same autonomous system. For instance, FIG. 1 shows two network areas, A0 and A1, in an autonomous system (AS) 100. Routers R1, R2, and R3 are linked in network area A0. Routers R3, R4, and R5 are linked in network area A1. Whenever an interface is brought up or a change in routing information known to one of the routers occurs, the router generates a LSA to inform its neighbors of the new or changed link-state information. When a neighbor router receives the LSA, it updates its own link-state database and then propagates the information in another LSA to its other neighbors. Thus the LSA is flooded to all routers in the same network area, and all routers in the same area contain the same link-state database. An area border router (ABR) such as R3 can have interfaces in multiple areas of an autonomous system, with different link-state databases synchronized to each area. Router R3 will generally choose to summarize information from one area for presentation to the other area.
The routers in an AS generate LSAs of various types, depending on their location in the AS. A Type 1 LSA contains information specific to the area to which the interface belongs, and is flooded throughout the area. A Type 2 LSA describes a set of routers attached to a particular network, and is also flooded to the area containing the network. Type 1 and type 2 LSAs are OSPF internal routes.
Type 3 and type 4 LSAs contain summaries of routes in a different area (inter-area routes) reachable through an ABR. An ABR generates a type 3 LSA in an area to advertise a route to a network in another area but reachable through the ABR. For instance, R3 would generate a type 3 LSA in area 0 to advertise the network in area 1 that contains R4 and R5. An ABR generates a type 4 LSA to advertise a route to an ASBR (an autonomous system boundary router, which provides routes outside of the AS) in another area.
Type 5 and type 7 LSAs describe routes external to the AS. An ASBR generates type 5 LSAs to redistribute routes received from another AS or another routing protocol. External routes are flooded throughout the AS, except for stub areas, which by definition do not receive type 5 LSAs. A type 7 LSA advertising an external route can, however, be generated using an ASBR in a Not So Stubby Area (NSSA). The NSSA propagates the type 7 LSA internally. An ABR converts the LSA to a type 5 LSA at the area boundary. LSAs of each of these types are used to synchronize the link state databases in each area of an AS.
FIG. 2 shows an exchange of OSPF protocol packets used to form an adjacency between two nodes, e.g., nodes R1 and R2 in FIG. 1. Initially, the state of the adjacency is DOWN. One of the nodes (in this example R1) begins the OSPF exchange by sending an OSPF Hello packet to the other (R2 in this example). R2 receives the hello, moves the link connecting R2 to R1 to an INIT state, and sends a return Hello packet to R1, acknowledging the Hello packet from R1.
The two routers next begin a database exchange process. One of the routers is determined to be the master (in this case R2) for a Database Description exchange during the exchange start (EXSTART) process. The slave router R1 in this example first enters the EXSTART state, and sends a first database description packet, with a sequency number y, to the master router R2. The master router discovers that it is to be the master, ignores database description packet y, enters the EXSTART state, and sends a first database description packet, with sequence number x, to R1. The database description packet contains link state advertisements (LSAs) for routes contained in R2's link state database. Each LSA indicates the LS age (the age since the advertisement was originated), the LS type, the LS ID (an IP address or other identifier), the identity of the router that originated the LSA, a checksum, and a LS sequence number, used to distinguish older/newer advertisements for the same LS ID.
The slave router R1 returns a database description packet with the same sequence number x (it must return a database description packet each time it is sent one), containing LSAs from its link state database. This process continues, e.g., for n+1 exchanges, until both routers indicate that they have no more routes to advertise. When one router finishes before the other, it continues to send empty database description packets until the other finishes.
Each router compares the LSAs it receives to the contents of its database. If any of the items in its local database have a lower sequence number than an LSA with the same LS ID, or are missing from the local database, the router requests a link state update from its neighbor. In the FIG. 2 example, it is assumed that R1 did not advertise anything that R2 did not already know about. Consequently, R2 enters a FULL state immediately after the exchange process and considers an adjacency to have been formed with R1. R1, however, identifies items that it needs from R2's database, and creates a list of LSAs corresponding to these items. R1 enters a LOADING state, in which it builds link state request packets (LSRs) containing LSAs from the list and transmits these to R2. R2 responds with link state update packets, which contain a full description of the requested link state items. This exchange continues until R1 exhausts its list, at which time it also enters a FULL state and considers the adjacency to be formed. It is also noted that R1 can issue an LSR at any time, even during the database description exchange, to receive full LSA information for items advertised by its peer.